package lc_1334_阈值距离内邻居最少的城市;

import java.util.Arrays;

public class SolutionDijkstra {

	public int findTheCity(int n, int[][] edges, int distanceThreshold) {
		int[][] nexts = new int[n][n];
		for (int i = 0; i < n; i++) {
			Arrays.fill(nexts[i], Integer.MAX_VALUE / 2);
		}
		for (int[] e : edges) {
			int a = e[0], b = e[1], d = e[2];
			nexts[a][b] = nexts[b][a] = d;
		}
		boolean[][] vis = new boolean[n][n];
		for (int i = 0; i < n; i++) {
			nexts[i][i] = 0;
			vis[i][i] = true;
			for (int k = 0; k < n - 1; k++) {
				int p = -1;
				for (int t = 0; t < n; t++) {
					if (!vis[i][t] && (p == -1 || nexts[i][t] < nexts[i][p])) {
						p = t;
					}
				}
				for (int j = 0; j < n; j++) {
					nexts[i][j] = Math.min(nexts[i][j], nexts[i][p] + nexts[p][j]);
				}
				vis[i][p] = true;
			}

		}
		int ans = -1, sum = Integer.MAX_VALUE;
		for (int i = 0; i < n; i++) {
			int cnt = 0;
			for (int j = 0; j < n; j++) {
				if (nexts[i][j] <= distanceThreshold) {
					cnt++;
				}
			}
			if (cnt <= sum) {
				sum = cnt;
				ans = i;
			}
		}
		return ans;

	}

	public static void main(String[] args) {
		SolutionDijkstra s = new SolutionDijkstra();
		s.findTheCity(4, new int[][] { { 0, 1, 3 }, { 1, 2, 1 }, { 1, 3, 4 }, { 2, 3, 1 } }, 4);
	}

}